1. Field of the Invention
The present invention relates generally to a content addressable memory and, more specifically, it relates to a content addressable memory in which the retrieval operation can be more correctly carried out.
2. Description of the Prior Art
As is generally known, the content addressable memory device (hereinafter abbreviated as CAM) is a memory device which is also called an associative memory. Data is retrieved from a CAM using a part of the data content to find a position in which the content is stored, and designating part of the content to take out the remaining content.
More specifically, the CAM compares the data stored in each memory cell of the CAM with the retrieval data used for the retrieval and when they coincide with each other, it outputs required information from that address where the coincidence occurs.
Usually, data is written by external normal writing operation in the memory cell array of the CAM. In some cases, however, some data stored in the memory cell array of the CAM cannot be known externally. The existence of such unknown data is not desirable. Namely, when the retrieval data is applied to the memory cell array, the stored data may possibly coincide with the retrieval data. In that case, correct retrieval information cannot be obtained.
Even if all memory cells in the array of the CAM are reset by a signal "0" in order to solve the problem, when the retrieval data having all signals being "0" is applied to the memory cell array, these data coincide with each other, causing incorrect result of retrieval.
As described above, a conventional CAM has a disadvantage that the result of the retrieval is not always correct. In addition, complicated control of the CAM is required in order to avoid the above mentioned disadvantage.
Prior Arts of particular interest to solve these problems will be briefly described in the following.
FIG. 1 is a block diagram showing an associative memory LSI disclosed in the Journal of Institute of Electronics and Communication Engineers of Japan by Takeshi (semiconductor transistor) on Dec. 1, 1983, pp. 45-52 by Takeski Ogura et al.
Referring to FIG. 1, the associative memory comprises a cell array 90, a bit line signal processing system 91 connected to the cell array 90 and a word line signal processing system 92 connected to the cell array 90. The word line signal processing system 92 comprises a write enable tag 93 for indicating whether the data of the word is necessary or not for each of the words in the cell array 90. By retrieving the write enable tag 93, a word which can be written (i.e. there is no need of holding the data) can be found from the cell array 90. Therefore, when new data should be written, the word to be written can be easily found without designation or administration of the address of the cell array by the CPU. Namely, in this operation, the address need not be controlled from outside of the associative memory.
The disclosed prior art associative memory simplifies the control in the writing operation, but does not solve the above described problems in the retrieval operation. Although the write enable tag 93 is not described in detail, it seems to be a collection of registers provided separately from the cell array 90, and a control circuit for controlling the write enable tag may be separately required.
Japanese Patent Laying-Open Gazette No. 57-74889 discloses a content similar to the prior art of FIG. 1.
An example of the prior art of particular interest is also disclosed in "Design of a Fast Cellular Associative Memory for Ordered Retrieval" by C. V. RAMAMOORTHY et al. published in September 1978 (IEEE TRANSACTIONS ON COMPUTERS, VOL. C-27, No. 9, pp. 800-815). This article also shows a flag register for each word provided separately from the memory cell array. As described above, when a register is employed as an element constituting the flag, a separate control circuit must be provided for controlling the same.
Another example of the prior art of particular interest is disclosed in "An 8-K bit Content-Addressable and Reentrant Memory" by HIROSHI KADOTA et al. published in October 1985 (IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL. SC-20, No. 5, pp. 951-956). In this article, the memory region of the memory cell array is divided into an occupied region in which data are written and a non-occupied region in which no data is written. A method for effectively administering the memory region of the CAM by controlling the writing operation into the occupied and non-occupied regions is disclosed.